package com.czk.algorithm.kruskal.practice;

import java.util.Arrays;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/9/13 16:01
 */
public class KruscalDemo {
}

/**
 * 克鲁斯卡尔算法
 */
class Kruscal{
    private int edgeNum;
    private char[] vertex;
    private int[][] matrix;
    private static final int Max_Num=Integer.MAX_VALUE;

    public Kruscal(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
        for (int i = 0; i < this.vertex.length; i++) {
            for (int j = i+1; j < this.vertex.length; j++) {
                if (this.matrix[i][j]!=Max_Num){
                    edgeNum++;
                }
            }
        }
    }
    /**
     * 排序边
     */
    public void sortEdge(Edata[] edata){
        // 冒泡排序
        for (int i = 0; i < edata.length-1; i++) {
            for (int j = 0; j < edata.length-i-1; j++) {
                if (edata[j].weight>edata[j+1].weight){
                    Edata temp;
                    temp=edata[j+1];
                    edata[j+1]=edata[j];
                    edata[j]=temp;
                }
            }

        }

    }
    /**
     * 返回·顶点对应的下标
     */
    public int getPosition(char ch){
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i]==ch){
                return i;
            }
        }
        return -1;
    }
    public Edata[] getEdge(){
        int index=0;
        // 创建数组
        Edata[] edata=new Edata[this.edgeNum];
        for (int i = 0; i < vertex.length; i++) {
            for (int j = i+1; j < vertex.length; j++) {
                if (matrix[i][j]!=Max_Num){
                    edata[index]=new Edata(vertex[i],vertex[j],matrix[i][j]);
                    index++;
                }
            }
        }
        // 排序
        this.sortEdge(edata);
        return edata;
    }
    /**
     * 获取下标为i的定顶点的终点，用于判断两个顶点的终点是否相同
     * @param ends 记录了哪个顶点的终点是哪一个，在数组遍历的过程中逐步形成
     * @param i 顶点的下标
     * @return 返回顶点对应终点对应的的下标
     */
    public int getEnd(int[] ends,int i){
        while (ends[i]!=0){
            i=ends[i];
        }
        return i;
    }
    public void kruscal(){
        // 用于保存终点索引
        int index=0;
        // 结果数组
        Edata[] result=new Edata[edgeNum];
        // 终点数组
        int[] ends=new int[edgeNum];
        // 获取所有边的集合
        Edata[] edata = this.getEdge();
        // 遍历边，添加到最小生成树中，同时要判断回路，如果没有，就加入结果数组中，否在就不能加入
        for (int i = 0; i < edgeNum; i++) {
            // 获取第i条边的一个顶点
            // 拿到该条边的起点
            char start = edata[i].start;
            // 拿到其索引
            int p1 = this.getPosition(start);
            // 拿到另一个顶点的起点和终点
            int p2 = this.getPosition(edata[i].end);
            // 拿到p1这个顶点的终点
            int m = this.getEnd(ends, p1);
            // 拿到p2这个顶点的终点
            int n = this.getEnd(ends, p2);
            // 判断是否构成回路
            if (m!=n){
                // 没有构成回路
                // 记录m的终点为n
                ends[m]=n;
                result[index++]=edata[i];
            }
        }
        System.out.println(Arrays.toString(result));
    }

    public static void main(String[] args) {
        char[] vertex={'A','B','C','D','E','F','G'};
        int[][] matrix={
                // A B C D  E F G
                {0,12,Max_Num,Max_Num,Max_Num,16,14},
                {12,0,10,Max_Num,Max_Num,7,Max_Num},
                {Max_Num,10,0,3,5,6,Max_Num},
                {Max_Num,Max_Num,3,0,4,Max_Num,Max_Num},
                {Max_Num,Max_Num,5,4,0,2,8},
                {16,7,6,Max_Num,2,0,9},
                {14,Max_Num,Max_Num,Max_Num,8,9,0}
        };
        // 创建对象实例
        Kruscal kruscal=new Kruscal(vertex,matrix);
        //kruscal.print();
       // Edata[] edge = kruscal.getEdge();
        //System.out.println(Arrays.toString(edge));
        kruscal.kruscal();
    }
}
/**
 * 创建边
 */
class Edata{
     char start;
     char end;
     int weight;

    public Edata(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Edata{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
